package leetcode101_xqzhao

// TODO 二叉树的层序遍历 【-】 队列

func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}
	// 定义一个队列
	queue := make([]*TreeNode, 0)
	// 将根节点放入队列
	queue = append(queue, root)
	// 保存结果
	res := make([][]int, 0)
	length := len(queue)

	for length != 0 {
		valQueue := make([]int, 0)

		for i := 0; i < length; i++ {
			// 取出队列第一个 Node
			tmpNode := queue[0]
			valQueue = append(valQueue, queue[0].Val)
			queue = queue[1:]
			if tmpNode.Left != nil {
				queue = append(queue, tmpNode.Left)
			}
			if tmpNode.Right != nil {
				queue = append(queue, tmpNode.Right)
			}
		}
		res = append(res, valQueue)
		length = len(queue)
	}

	return res
}
